package sort;

import java.util.Arrays;

/**
 * 快排算法
 * @author Tang Jiujia
 * @since 14:04 2020-04-13
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 3, 7, 5, 15, 9, 11, 6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        int len = arr.length;
        quickSort(arr, 0, len - 1);
    }

    /**
     * 快排递归函数
     *
     * @param arr
     * @param p
     * @param r
     */
    private static void quickSort(int[] arr, int p, int r) {
        if (p >= r) {return;}
        int q = partition(arr, p, r);
        quickSort(arr, p, q - 1);
        quickSort(arr, q + 1, r);
    }

    /**
     * 分区函数, 将数组分区，按分区排序，这里采用原地分区
     *
     * @param arr
     * @param p
     * @param r
     * @return int 分区点
     */
    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (arr[j] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        //最后交换arr[i]和arr[r]
        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
        return i;
    }
}




